/*
Maximum Product Subarray Total Accepted: 32936 Total Submissions: 169783 My Submissions Question Solution
Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


class Solution {
public:
	int maxProduct(vector<int>& nums) {
		if (nums.size()==0)
		{
			return 0;
		}
		if (nums.size() ==1)
		{
			return nums[0];

		}
		int curMax = nums[0];
		int curMin = nums[0];
		int res = nums[0];
		for (int i = 1; i < nums.size(); i++)
		{
			int temp = curMin*nums[i];
			curMin = min(nums[i], min(temp, curMax*nums[i]));
			curMax = max(nums[i], max(temp, curMax*nums[i]));
			res = max(res, curMax);


		}

		return res;
	}
};

int main(int argc, char* argv[])
{


	int a[] = {2,3,-2,4};
	vector<int> vec(a, a + sizeof(a) / sizeof(int));


	int result;
	Solution s;
	result = s.maxProduct(vec);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;